/**
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 *
 * 叶子节点 是指没有子节点的节点。
 *
 * https://leetcode.cn/problems/path-sum-ii/
 */
class PathSumTwo {
    List<List<Integer>> ret=new LinkedList<>();
    Deque<Integer> path=new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root,targetSum);
        return ret;
    }
    public void dfs(TreeNode root,int targetSum){
        if(root==null){
            return ;
        }
        path.offerLast(root.val);
        targetSum-=root.val;
        if(root.left==null&&root.right==null&&targetSum==0){
            ret.add(new LinkedList<Integer>(path));
        }
        dfs(root.left,targetSum);
        dfs(root.right,targetSum);
        path.pollLast();
    }
}